//https://leetcode.cn/problems/binary-tree-postorder-traversal/
package codeRandomThoughts.Test145二叉树的后序遍历;

import codeRandomThoughts.utils.TreeNode;

import java.util.*;

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        //先用栈存储遍历的集合
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pt = root;
        TreeNode right = pt.right;
        while (pt != null || !stack.isEmpty()) {
            if (pt != null) {
                stack.push(pt);
                right = pt.right;
                pt = pt.left;
            } else {
                if (right != null) {
                    pt = right;
                } else {
                    TreeNode pop = stack.pop();
                    if (!stack.isEmpty() && pop != stack.peek().right) {
                        //添加右兄弟
                        pt = stack.peek().right;
                    }
                    list.add(pop.val);
                }
            }
        }
        return list;
    }

    public List<Integer> postorderTraversal2(TreeNode root) {

        TreeNode p = root, r = null;
        List<Integer> ans = new ArrayList();
        Deque<TreeNode> s = new ArrayDeque();
        while (!s.isEmpty() || p != null) {
            if (p != null) {
                s.push(p);
                p = p.left;
            } else {
                p = s.peek();
                if (p.right == null || p.right == r) {
                    ans.add(p.val);
                    r = p;
                    s.pop();
                    p = null;
                } else
                    p = p.right;

            }

        }

        return ans;
    }

    public List<Integer> postorderTraversal3(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node != null) {
                stack.pop();
                stack.push(node);                            //根
                stack.push(null);
                if (node.right != null) stack.push(node.right);//右
                if (node.left != null) stack.push(node.left);  //左
            } else {
                stack.pop();//把空指针pop出去
                list.add(stack.pop().val);
            }
        }
        return list;
    }
}